/*
 * prefix_list Reverse Lexicographically Sorted Prefix
 * Copyright 2008 Jonathan Masci
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */

#include <string.h>
#include <stdlib.h>
#include <stdio.h>
#include <assert.h>
#include <limits.h>
#include <time.h>

/**
 * \typedef uint
 */
typedef unsigned int uint;
/**
 * \typedef uchar
 */
typedef unsigned char uchar;

/**
 * \typedef node
 * \brief The node of the prefix_list.
 */
typedef struct node_type {
  struct node_type *next;
  struct node_type *prev;
  struct node_type *succ;
  uint text_pos;
  uint lcp;
} node;

/**
 * \typedef prefix_list
 * \brief The reverse lexicographically sorted prefixes list.
 */
typedef struct prefix_list_type {
  node *head;
  node *tail;
  node *last_inserted;
  node *symbol_ptr[256]; // for uint symbols range
  uchar *text;
  int biggest_sym;
  int smallest_sym;
} prefix_list;

/**
 * \brief Read a file to a buffer and set its length.
 *
 * \param filename: the path
 * \param textt: a pointer to the buffer that will be filled in
 * \param length: where to store the length
 * \return 0 on success or 1 on error
 */
int read_file(char *filename, uchar **textt, uint *length) {
  uchar *text;
  uint t;
  FILE *infile;

  infile = fopen(filename, "rb");

  if (infile == NULL) {
    return 1;
  }

  // store input file length
  if (fseek(infile, 0, SEEK_END) !=0) {
    return 1;
  }
  *length = ftell(infile);

  // alloc memory for text
  text = (uchar *) malloc ((*length) * sizeof(uchar) + 1);
  if (text == NULL) {
    return 1;
  }

  //read text in one sweep
  rewind(infile);
  t = fread(text, sizeof(uchar), (size_t) *length, infile);
  if (t != *length) {
    return 1;
  }
  text[*length] = '\0';
  *textt = text;
  fclose(infile);

  return 0;
}

/**
 * \brief Return a substring of the given string.
 *
 * \param str: the string
 * \param start: start position (it is included in the substring)
 * \param end: end position (it is included in the substring)
 * \param len: the len of the text
 * \param ret_substring: the substring
 * \return 0 on success of exit by assert on error
 */
inline int substring(const uchar *str, int start, int end, int len, uchar **ret_substring) {
  assert(start < len);
  assert(end < len);

  uchar *t;
  uint i;

  if (start > end) {
    t = (uchar *)malloc(start - end + 2);
    for (i = start; i <= start; --i) {
      t[start - i] = str[i];
    }
    t[start - end + 1] = '\0';
  } else {
    t = (uchar *)malloc(end - start + 2);
    for (i = start; i <= end; ++i)
      t[i - start] = str[i];
    t[end - start + 1] = '\0';
  }
  *ret_substring = t;
  return 0;
}

/**
 * \brief Computes the backward longest common prefix of the prefixes
 * indicates by their starting position within the same text.
 *
 * \param pos1: position of the first prefix
 * \param pos2: position of the second prefix
 * \param str: the string to look at for lcp
 * \param ret_len: the length of the match
 * \return 0 on success
 */
inline int bw_lcp(uint pos1, uint pos2, uchar *str, uint *ret_len) {
  uint min = (pos1 > pos2 ? pos2 : pos1);
  uint blcp = 0;

  while (blcp <= min && str[pos1 - blcp] == str[pos2 - blcp])
    blcp++;
  *ret_len = blcp;
  return 0;
}

/**
 * \brief Create a new prefix_list and return it via pl parameter.
 *
 * \param pl: a pointer to a prefix_list pointer where the new prefix_list will
 *            be returned
 * \param text: the text to associate to the prefix_list
 * \return 0 on success
 */
int prefix_list_new(prefix_list **pl, uchar **text) {
  prefix_list *tmp_list = (prefix_list *)malloc(sizeof(*tmp_list));
  node *head = (node *)malloc(sizeof(*head));
  node *tail = (node *)malloc(sizeof(*tail));
  head->next = tail->next = NULL;
  head->succ = tail;
  head->prev = tail->succ = NULL;
  tail->prev = head;
  head->text_pos = tail->text_pos = 0;
  head->lcp = tail->lcp = 0;
  tmp_list->head = head;
  tmp_list->tail = tail;
  tmp_list->last_inserted = head;
  memset(tmp_list->symbol_ptr, 0, 256);
  tmp_list->biggest_sym = -1;
  tmp_list->smallest_sym = INT_MAX;
  tmp_list->text = *text;
  *pl = tmp_list;
  return 0;
}

/**
 * \brief Remove completely the list and free all the memory.
 *
 * \param pl: prefix_list to delete.
 * \return 0 on success.
 */
int prefix_list_free(prefix_list *pl) {
  node *it = pl->head->succ;

  while (it != pl->tail) {
    free(it->prev);
    it = it->succ;
  }
  //head and last_inserted freed before
  free(pl->tail);
  free(pl->text);

  return 0;
}

/**
 * \brief Insert a node after another node already in the list.
 * It also updates the longest common prefix of the nodes.
 *
 * \param pl: the prefix_list where new_node will be inserted
 * \param new_node: the node to insert
 * \param nod: the node after which new_node will be inserted
 * \return 0 on success
 */
int prefix_list_add_after(prefix_list *pl, node *new_node, node *nod) {
  assert(nod != pl->tail);

  node *tmp_tail = pl->tail;
  nod->succ->prev = new_node;
  new_node->succ = nod->succ;
  nod->succ = new_node;
  new_node->prev = nod;
  pl->last_inserted->next = new_node;
  new_node->next = NULL;
  pl->last_inserted = new_node;

  // Some checks
  assert(tmp_tail == pl->tail);
  assert(pl->tail->succ == NULL);
  assert(pl->head->prev == NULL);

  /**
   * Update the lcp of the current node and of the previous node.
   * The backward longest common prefix is computed on text_pos - 1
   * because of the reserved 0 value;
   */
  uint len = 0;
  bw_lcp(new_node->text_pos - 1, new_node->succ->text_pos - 1, pl->text, &len);
  new_node->lcp = len;
  bw_lcp(new_node->prev->text_pos - 1, new_node->text_pos - 1, pl->text, &len);
  new_node->prev->lcp = len;

  return 0;
}

/**
 * Insert a node before another node already in the list.
 * It simply goes to the previous node, and i can always do it because
 * of the head node, and do a prefix_list_add_after.
 *
 * \param pl: the prefix_list where new_node will be inserted
 * \param new_node: the node to insert
 * \param nod: the node before which new_node will be inserted
 * \return 0 on success
 */
int prefix_list_add_before(prefix_list *pl, node *new_node, node *nod) {
  assert(nod != pl->head);

  nod = nod->prev;
  prefix_list_add_after(pl, new_node, nod);

  assert(pl->tail->succ == NULL);
  assert(pl->head->prev == NULL);
  return 0;
}

/**
 * Add the prefix that starts from text_pos within the prefix_list
 * associated text.
 *
 * When we create a prefix_list, we pass a text to it (uchar*), and
 * then we add a prefix of that text using this function.
 *
 * \param pl: the prefix_list where to add the prefix of its text
 * \param text_pos: the position of the prefix
 * \return 0 on success or it will exit(1) on error
 */
int prefix_list_add(prefix_list **pl, uint text_pos) {
  prefix_list *tmp_list = *pl;
  uchar *text = tmp_list->text;
  /**
   * Integer value of the current text_post char to see if it is
   * an already seen one and if it is biggest or smallest.
   */
  int pos_sym = (int)text[text_pos];
  /**
   * The position of the text that will be stored in the node.
   * Note that it is offsetted by 1.
   */
  int i = pos_sym + 1;
  /** The node found looking upside the list. */
  node *up_find = NULL;
  /** The node found looking downside the list. */
  node *down_find = NULL;
  /** Temporary placeholder to search upside */
  node *up_search = NULL;
  /** Temporary placeholder to search downside */
  node *down_search = NULL;
  /** The new node */
  node *nod = (node *)malloc(sizeof(*nod));
  nod->text_pos = text_pos + 1;
  nod->lcp = -1;
  nod->next = nod->prev = nod->succ = NULL;

  if (tmp_list->symbol_ptr[pos_sym] == NULL) {
    /**
     * It is not an already seen symbol so we put the node in the
     * position indicated by its integer conversion.
     */
    tmp_list->symbol_ptr[pos_sym] = nod;

    /**
     * It is the new smallest symbol.
     * Update the smallest_sym field of the prefix_list and if it is
     * the first symbol ever update biggest_sym also.
     */
    if (pos_sym < tmp_list->smallest_sym) {
      prefix_list_add_after(tmp_list, nod, tmp_list->head);
      tmp_list->smallest_sym = pos_sym;
      if (tmp_list->biggest_sym == -1)
        tmp_list->biggest_sym = pos_sym;
      return 0;
    }
    /**
     * It is the new biggest symbol.
     * Update the biggest_sym field of the prefix_list and if it is
     * the first symbol ever update smallest_sym also.
     */
    if (pos_sym > tmp_list->biggest_sym) {
      prefix_list_add_before(tmp_list, nod, tmp_list->tail);
      tmp_list->biggest_sym = pos_sym;
      if (tmp_list->smallest_sym == -1)
        tmp_list->smallest_sym = pos_sym;
      return 0;
    }
    /**
     * We look for its next integer converted value and then we'll insert the
     * node just before this one.
     */
    while (i < 256) {
      if (tmp_list->symbol_ptr[i] != NULL) {
        prefix_list_add_before(tmp_list, nod, tmp_list->symbol_ptr[i]);
        i = -1;
        break;
      }
      ++i;
    }
    //if (i != -1) {
    //  prefix_list_add_before(tmp_list, nod, tmp_list->symbol_ptr[pos_sym]);
    //}
  } else {
    /**
     * We search for the right position of node in the list using the
     * tecnique described before.
     *
     * We do alternate search to minimize the iterations.
     * In fact, if we'll do a naive search we could take the longest direction
     * when, looking just one position in the other direction
     * we'd match our search.
     */
    while (up_find == NULL && down_find == NULL) {
      // Search up following next pointers
      up_search = tmp_list->last_inserted->prev;
      while (up_search != NULL && up_find == NULL) {
        if (text[up_search->next->text_pos - 1] == text[text_pos])
          up_find = up_search;
        up_search = up_search->prev;
      }
      // Search down following next pointers
      down_search = tmp_list->last_inserted->succ;
      while (down_search != tmp_list->tail && down_find == NULL) {
        if (text[down_search->next->text_pos - 1] == text[text_pos])
          down_find = down_search;
        down_search = down_search->succ;
      }
    }
    if (up_find != NULL && down_find != NULL) {
      // The node have to be placed between up_find and down_find
      assert(up_find->next->succ == down_find->next);
      assert(up_find->next == down_find->next->prev);

      prefix_list_add_after(tmp_list, nod, up_find->next);
    } else if (up_find != NULL) {
      prefix_list_add_after(tmp_list, nod, up_find->next);
    } else if (down_find != NULL) {
      if (tmp_list->symbol_ptr[pos_sym] == down_find->next)
        tmp_list->symbol_ptr[pos_sym] = nod;
      prefix_list_add_before(tmp_list, nod, down_find->next);
    } else {
      printf("Error: up_find and down_find are NULL!\n");
      exit(1);
    }
  }
  return 0;
}
